package Javafoundation;

import java.util.*;

public class Topo {
    private class Vertex{
        private String vertex;
        private List<Edge> Edges;
        private int inDegree;

        public Vertex(String verTtexLabel) {
            this.vertex = verTtexLabel;
            inDegree = 0;
            Edges = new LinkedList<Edge>();
        }
    }

    private class Edge {
        private Vertex endVertex;
        public Edge(Vertex endVertex) {
            this.endVertex = endVertex;
        }
    }

    private Map<String, Vertex> directedGraph;

    public Topo() {
        directedGraph = new LinkedHashMap<String, Vertex>();
        buildGraph();
    }

    private void buildGraph(){

        Vertex startNode1, endNode1;
        String startNode2, endNode2;
        Edge e;
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入有向图的边数：");
        int m = scan.nextInt();

        for (int i = 0; i <m; i++) {
            System.out.println("请输入第"+(i+1)+"边的头和尾： ");
            startNode2 = scan.next();
            endNode2 = scan.next();
            startNode1 = directedGraph.get(startNode2);
            if (startNode1 == null)
            {
                startNode1 = new Vertex(startNode2);
                directedGraph.put(startNode2, startNode1);
            }
            endNode1 = directedGraph.get(endNode2);
            if (endNode1 == null)
            {
                endNode1 = new Vertex(endNode2);
                directedGraph.put(endNode2, endNode1);
            }

            e = new Edge(endNode1);
            startNode1.Edges.add(e);
            endNode1.inDegree++;
        }

    }

    public void topoSort() throws Exception{
        int count = 0;

        Queue<Vertex> queue = new LinkedList<>();
        Collection<Vertex> vertexs = directedGraph.values();
        for (Vertex vertex : vertexs)
            if(vertex.inDegree == 0)
                queue.offer(vertex);

        while(!queue.isEmpty() )
        {
            Vertex v = queue.poll();
            System.out.print(v.vertex + " ");
            count++;
            for (Edge e : v.Edges)
                if(--e.endVertex.inDegree == 0)
                    queue.offer(e.endVertex);
        }
        if(count != directedGraph.size() )
        {
            throw new Exception("该图存在环");
        }

    }
}
